Java 2D数组，查找包含元素

Question

我有一个2D数组声明如下：

private Dots[][] dots = new Dots[8][8];

我正在制作一个用于教育目的的游戏，2D数组中填充了点，每个点都有一个从四种颜色中随机选择的颜色。游戏的目标是将这些点连接起来。当你连接相同颜色的点时，它们会被删除，你会得到它们的点数。目前一切正常，但我想添加一个新功能：

关闭路径时，该路径中包含的所有点也将被删除。（见图）：

我正在考虑一个算法来找到路径中包含的所有点，但我想不出一个

路径存储在LinkedList中（可能与此无关，但我只是想确认一下：）

所以，总结一下我的问题：我试图提出一种算法，在蓝点之间选择灰点

注:

• 点可以对角连接
• 路径可以是玩家想要的长度
• 闭合路径可以是任何形状

编辑1： 这就是游戏的样子：

编辑2： 这就是我的意思：

When you close the path, all dots contained in that path will be deleted aswell.

Answer 1

动态规划方法（n^2）

对于任何符合计数条件的单元格，您需要（i，j-1），（i-1，j）和（i，j+1），（i+1，j）
注意：这个单元格不可能完全在那里，也可能在下面

创建一个布尔二维数组
让我们以6×6以下的样本为例
/*
T----
T-T----
T----
-T---
-T---
*/
其中T表示闭合路径

2次迭代：
第一名

首先遍历矩阵，如果发现（i，j-1）和（i-1，j）为真，则将该点包含在集合中（或任意集合）。 因为边界条件不包括在集合中，因为它们永远不会在闭合路径中，所以在第一次迭代结束时，您将

/*
T F
t1 T F
T F
F T 1 F F
F T 1 F F
*/
其中1表示集合中包含的点
（这里您可能希望使用字符2d矩阵而不是布尔值。但是，如果您使用布尔值，那么它也可以工作，只需要执行set.contains（新点（i，j）））

第二名

做同样的事情，但是从（n-1，n-1）开始，这次你检查（i+1，j），（i，j+1）点是否为真。对于二维矩阵中的任何点，若你们发现它应该是“F”，但它是“1”，那个么从集合中移除该点

/*
T F
t1 T F
T F
F T F
F T F
*/

因此，在2次n^2操作之后。您将拥有包含所需点的集合

yes 1也将作为后续迭代的T
简言之，与DP不同的是，我们从左上到右下，从右下到左上，以找出闭合路径内的确切点
F-不合格
T-仅可计数
1-与T相同，但也被添加到输出集中

Answer 2

• 固溶体：

正确的解决方案是实施4-connected/4-neighbor版本的洪水填充算法

它非常漂亮。 java中的一个例子可以是found here.

• 朴素的解决方案：

逐行，将所有字段最初着色为白色，然后用户选择蓝色，并逐行迭代，将中间的字段（状态：boolean select = true）着色为灰色：

enum COLOR { BLUE, GREY, WHITE}; 

boolean select = false;

// iterate row by row
for(int x = 0; x < 8; x++) {
       for(int y = 0; y <8; y++) {
           //select mode...
           if(dots[x][y].color == COLOR.BLUE  && !change) {
                select = true;
           }
           //if we are in select and the current field is white -> make GREY
           if(select && dots[x][y].color == COLOR.WHITE) {
                dots[x][y].color = COLOR.GREY;
           }
           // if we hit another blue and are in select -> select = false
           if(select && dots[x][y].color == COLOR.BLUE) {
                select = false;
           }
    }
}

注：仍有一些案例有待解决：

例如，如果当前迭代行的长度为垂直蓝色墙，且长度为奇数，则错误地变为选择模式